#include "MergeSort.h"
#include "my_limits.h"


void
Merge_sort__merge(int* a, int L, int M, int R)
{
	register int i = L,
		     j = M+1,
		     s = 0; /* index. points to where we will place next element */
	int sorted[SEQ_MAXLEN];

	while (i <= M || j <= R) {
		if (a[i] < a[j]) {
			if 	(i <= M)
				sorted[s++] = a[i++];
			else if (j <= R)
				sorted[s++] = a[j++];
		} else {
			if 	(j <= R)
				sorted[s++] = a[j++];
			else if (i <= M)
				sorted[s++] = a[i++];
		}
	}

	i = 0;
	while (i < s) {
		a[L + i] = sorted[i];
		++i;
	}
}



void
Merge_sort__main(int* a, int L, int R)
{
	int M;
	if (L < R) {
		M = (L + R) / 2;

		Merge_sort__main(a, L, M);
		Merge_sort__main(a, M+1, R);

		Merge_sort__merge(a, L, M, R);
	}
}



void
Merge_sort(int * array, int size)
{
	return Merge_sort__main(array, 0, --size);
}

